Voice message services are being widely implemented in today's telephone networks. Callers have increasingly found that voice messaging provides a valuable communication service. Under some circumstances, however, callers are reluctant to utilize the service because they are not certain that their intended recipient ever received their message. In such a situation, a person-to-person call may not be possible because the called party's line is busy, or may not be considered by the caller because of the time zone difference between the caller and called party. Thus, a problem exists which is not adequately addressed by existing voice messaging and person-to-person telephone services.